package com.hy.day;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * <p>
 * User:Mr.Du
 * Date:2024/7/30
 * Time:9:11
 */
public class GetGoodIndices {

    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i < variables.length;i++){
            int a = variables[i][0], b = variables[i][1],
                    c = variables[i][2], m = variables[i][3];
            long a_b_mod_10 = fastModExp(a, b, 10);
            // 计算 (a^b % 10)^c % m
            long result = fastModExp(a_b_mod_10, c, m);
            if(result == target){
                res.add(i);
            }
        }
        return res;
    }

    // 计算 (base^exp) % mod
    public static long fastModExp(long base, long exp, long mod) {
        long result = 1;
        base = base % mod; // 处理基数模
        while (exp > 0) {
            if ((exp % 2) == 1) { // 如果 exp 是奇数
                result = (result * base) % mod;
            }
            exp = exp >> 1; // exp 除以 2
            base = (base * base) % mod; // base 平方
        }
        return result;
    }

    /**
     * 实现快速幂算法，计算一个数的幂次方。
     * 快速幂算法通过拆分幂次方的指数，利用乘法的结合律和交换律，将一个大指数的幂运算转化为多个小指数的幂运算的乘积，
     * 从而降低时间复杂度，提高运算效率。
     *
     * @param x 底数，可以是任意实数。
     * @param N 幂次方的指数，可以是整数。当N为负数时，等价于计算1/x的绝对值的幂次方。
     * @return 返回底数x的N次幂的结果。
     */
    public double myPow(double x, int N){
        // 将N赋值给n，后续操作基于n进行，这样可以避免在条件判断中反复对N进行操作。
        int n = N;
        // 初始化结果res为1，因为任何数的0次幂都是1。
        double res = 1;

        // 当指数N为负数时，进行特殊处理，将n变为正数，同时将x变为倒数。
        if(n < 0){
            n = -n;
            x = 1 / x;
        }

        // 利用循环进行幂次方的计算，当n大于0时继续循环。
        while(n > 0){
            // 如果n的当前最低位为1（即n是奇数），则将当前的x乘到结果res上。
            if((n & 1) == 1){
                res *= x;
            }
            // 将x自乘，相当于将x的幂次方提高一倍。
            x *= x;
            // 将n右移一位，相当于将n除以2，这是因为我们在上一步中已经处理了n的最低位。
            n >>= 1;
        }

        // 循环结束后，返回计算得到的幂次方结果。
        return res;
    }
}
